#pragma once
#include "DenseGraph.h"
#include "SparseGraph.h"

template<typename Graph>
class DFS
{
public:
	DFS(Graph& G) : g(G)
	{
		visited = new bool[g.V()];
		ccount = 0;
		for (int i = 0; i < g.V(); ++i)
		{
			visited[i] = false;
		}
		for (int i = 0; i < g.V(); ++i)
		{
			if (!visited[i])
			{
				DoDFS(i);
				ccount++;
			}
		}
	}

	~DFS()
	{
		delete[] visited;
	}

	void DoDFS(int v)
	{
		visited[v] = true;
		typename Graph::adjIterator it(g, v);
		for (int i = it.begin(); !it.end(); i = it.next())
		{
			if (!visited[i])
			{
				DoDFS(i);
			}
		}
	}

	int Count() { return ccount; }

private:
	Graph& g;
	bool *visited;
	int ccount;
};